#include<stdio.h>
#include<stdlib.h>
typedef enum { false, true } bool;

/*图的邻接矩阵表示法*/
#define MaxVertexNum 1000/*最大顶点数*/
typedef int Vertex;/*用顶点下标表示顶点，为整型*/
typedef int WeightType;/*边的权值为整型*/

/*边的定义*/
typedef struct ENode* PtrToENode;
struct ENode {
	Vertex V1, V2;/*有向边<V1，V2>*/
};
typedef PtrToENode Edge;

/*图结点的定义*/
typedef struct GNode* PtrToGNode;
struct GNode {
	int Nv;/*顶点数*/
	int Ne;/*边数*/
	WeightType G[MaxVertexNum][MaxVertexNum];/*邻接矩阵*/
	int Degree[MaxVertexNum];/*存顶点的度*/
};
typedef PtrToGNode MGraph;/*以邻接矩阵存储的图类型*/
bool Visited[MaxVertexNum];/*顶点的访问标记*/

MGraph CreateGraph(int VertexNum);/*构造一个有VertexNum个顶点没有边的图*/
void InsertEdge(MGraph Graph, Edge E);/*在图Graph中增加新边E*/
MGraph BuildGraph();/*构造一个完整（有顶点，有边）的图*/
void DFS(MGraph Graph, Vertex V);/*在图Graph中，从顶点V出发进行深度优先遍历*/
bool CheckG(MGraph Graph);/*检查顶点的度是否全为偶数*/

int main()
{
	Vertex V;
	MGraph Graph = BuildGraph();
	DFS(Graph, 0);/*检查连通性*/
	for (V = 0; V < Graph->Nv; V++)
		if (!Visited[V]) 
			break;
	if (V < Graph->Nv)/*若有结点没被DFS访问到，则证明图不连通*/
		printf("0\n");
	else/*反之图连通*/
		printf("%d\n", CheckG(Graph));
	return 0;
}

MGraph CreateGraph(int VertexNum)
{
	Vertex V, W;
	MGraph Graph;
	Graph = (MGraph)malloc(sizeof(struct GNode));/*建立图*/
	Graph->Nv = VertexNum;
	Graph->Ne = 0;
	/*初始化邻接矩阵(顶点编号从0开始，到Graph->Nv-1结束)*/
	for (V = 0; V < Graph->Nv; V++) {
		Graph->Degree[V] = 0;
		for (W = 0; W < Graph->Nv; W++)
			Graph->G[V][W] = 0;
	}
	return Graph;
}

void InsertEdge(MGraph Graph, Edge E)
{
	/*插入边<V1，V2>*/
	Graph->G[E->V1][E->V2] = 1;
	Graph->Degree[E->V1]++;
	/*若为无向图，还要插入边<V2，V1>*/
	Graph->G[E->V2][E->V1] = 1;
	Graph->Degree[E->V2]++;
}

MGraph BuildGraph()
{
	MGraph Graph;
	Edge E;
	Vertex V;
	int Nv, i;
	scanf("%d", &Nv);
	Graph = CreateGraph(Nv);
	scanf("%d", &(Graph->Ne));
	/*如果有边*/
	if (Graph->Ne != 0) {
		E = (Edge)malloc(sizeof(struct ENode));/*建立边结点*/ 
		/*读入边(起点，终点)，插入邻接矩阵*/
		for (i = 0; i < Graph->Ne; i++) {
			scanf("%d %d", &E->V1, &E->V2);
			E->V1--;/*邻接矩阵顶点编号从0开始，输入的编号从1开始*/
			E->V2--;
			InsertEdge(Graph, E);
		}
	}
	return Graph;
}

void DFS(MGraph Graph, Vertex V)
{
	Vertex W;
	Visited[V] = true;
	for (W = 0; W < Graph->Nv; W++)
		if (!Visited[W] && (Graph->G[V][W]))/*当W尚未被访问且与V右边相连*/
			DFS(Graph, W);
}

bool CheckG(MGraph Graph)
{
	Vertex V;
	for (V = 0; V < Graph->Nv; V++)
		if (Graph->Degree[V] % 2)/*发现奇数度的边则返回0*/
			return false;
	return true;/*全是偶数度的边则返回1*/
}

